
/*
    55. 跳跃游戏
    动态规划+贪心
 */

public class CanJump {

    public static void main(String[] args) {
        int[] nums = {3,2,1,0,4};
        System.out.println(canJump(nums));
    }

    public static boolean canJump(int[] nums) {
//        int i = 0;
//        while (i < nums.length - 1 && nums[i] < (nums.length - 1 - i)) {
//            if (nums[i] == 0 && i != nums.length - 1) return false;
//            int target = nums[i];
//            int max = i + 1;
//            int index = i;
//            while (target > 0) {
//                index++;
//                max = nums[index] >= nums[max] ? index : max;
//                target--;
//            }
//            if (nums[i] > nums[max] && (nums[i + nums[i]] != 0 || i + nums[i] == nums.length - 1)) {
//                i = i + nums[i];
//            } else {
//                i = max;
//            }
//        }
//        return true;

        //动态规划
        int max = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int temp = i + nums[i];
            max = Math.max(max, temp);
            if (max >= nums.length - 1) return true;
        }
        return false;
    }
}
